//Given the head of a singly linked list, sort the list using insertion sort, an
//d return the sorted list's head. 
//
// The steps of the insertion sort algorithm: 
//
// 
// Insertion sort iterates, consuming one input element each repetition and grow
//ing a sorted output list. 
// At each iteration, insertion sort removes one element from the input data, fi
//nds the location it belongs within the sorted list and inserts it there. 
// It repeats until no input elements remain. 
// 
//
// The following is a graphical example of the insertion sort algorithm. The par
//tially sorted list (black) initially contains only the first element in the list
//. One element (red) is removed from the input data and inserted in-place into th
//e sorted list with each iteration. 
//
// 
// Example 1: 
//
// 
//Input: head = [4,2,1,3]
//Output: [1,2,3,4]
// 
//
// Example 2: 
//
// 
//Input: head = [-1,5,3,4,0]
//Output: [-1,0,3,4,5]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the list is in the range [1, 5000]. 
// -5000 <= Node.val <= 5000 
// 
// Related Topics 排序 链表 
// 👍 400 👎 0

package leetcode.editor.cn;

class P147InsertionSortList {
    public static void main(String[] args) {
        Solution solution = new P147InsertionSortList().new Solution();
        ListNode node1 = new ListNode(-1);
        ListNode node2 = new ListNode(5);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(0);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        solution.insertionSortList(node1);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode insertionSortList(ListNode head) {
            ListNode first = head;
            ListNode tail = head;
            ListNode curNode = head.next;
            int count = 0;
            while (curNode != null) {
                count++;
                ListNode nextNode = curNode.next;
                ListNode firstNode = first;
                ListNode preNode = firstNode;
                tail.next = null;
                while (firstNode != null && curNode.val >= firstNode.val) {
                    preNode = firstNode;
                    firstNode = firstNode.next;
                }
                if (first == firstNode) {
                    curNode.next = first;
                    first = curNode;
                    tail.next = null;
                } else {
                    preNode.next = curNode;
                    curNode.next = firstNode;
                    if (firstNode == null) {
                        tail = curNode;
                    }
                }
                curNode = nextNode;
            }
            return first;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}